/*
    Longest Commom Subsequence
    不一定是连续的公共子串！！！
    连续的算法要简单一些。
    另外还有办法在算出最长公共串长度之后，用回溯这个矩阵的方法输出这个
    最长公共串。
    但我懒得写了。有点复杂
*/

#include <iostream>
using namespace std;
#define SAME(a,b) ((a)==(b) ? 1 : 0)
#define MAX(a,b,c) ( (a)>(b) ? ((a)>(c)?(a):(c))          \
                       :  ((b)>(c)?(b):(c))                     \
                     )


int main()
{
    char a[] = " c";
    char b[] = "";
    int opt[10][10] ;

    int lenA = sizeof(a) / sizeof(char);    //这里的len 实际上还包括了\0这个字符
    int lenB = sizeof(b) / sizeof(char);
    int i;
    int j;
    for (i=0; i<lenA-1; i++)
    {
        for (j=0; j<lenB-1; j++)
        {
            if (i==0 && j==0)
            {
                opt[i][j] = SAME(a[i], b[j]);
            }
            else if (i==0)
            {
                opt[i][j] = MAX(   0 + SAME(a[i], b[j]),
                                   0,
                                   opt[i][j-1]
                               );
            }
            else if (j == 0)
            {
                opt[i][j] = MAX(   0 + SAME(a[i], b[j]),
                                   opt[i-1][j],
                                   0);
             }
             else
            {
                opt[i][j] = MAX(   opt[i-1][j-1] + SAME(a[i], b[j]),
                                   opt[i-1][j],
                                   opt[i][j-1]
                               );
            }
        }
    }
    if (i==0 || j==0)       //说明有一个串是空的。上面的循环没走
    {
        cout<<"LCS():"<<0<<endl;
    } else
    {
    cout<<"LCS():"<<opt[i-1][j-1]<<endl;
    }

}
